﻿#define _CRT_SECURE_NO_WARNINGS


//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//示例 1：
//输入：head = [1, 2, 3, 4, 5]
//输出：[5, 4, 3, 2, 1]
//示例 2：
//输入：head = [1, 2]
//输出：[2, 1]
//示例 3：
//输入：head = []
//输出：[]

//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* cur = head;
//    struct ListNode* prev = NULL;
//    while (cur)
//    {
//        struct ListNode* next = cur->next;
//        cur->next = prev;
//        prev = cur;
//        cur = next;
//    }
//    return prev;
//}

//找单链表的中间节点

//给你单链表的头结点 head ，请你找出并返回链表的中间结点。
//如果有两个中间结点，则返回第二个中间结点。
//示例 1：
//输入：head = [1, 2, 3, 4, 5]
//输出：[3, 4, 5]
//解释：链表只有一个中间结点，值为 3 。
//示例 2：
//输入：head = [1, 2, 3, 4, 5, 6]
//输出：[4, 5, 6]
//解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

//struct ListNode* middleNode(struct ListNode* head) {
//
//    struct ListNode* quick = head;
//    struct ListNode* slow = head;
//    while (quick && quick->next)
//    {
//        quick = quick->next->next;
//        slow = slow->next;
//    }
//    return slow;
//
//}

//
//输入一个链表，输出该链表中倒数第k个结点。
//示例1
//输入：
//1, { 1,2,3,4,5 }
//返回值：
//{ 5 }

//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//    // write code here
//    struct ListNode* fast = pListHead;
//    struct ListNode* show = pListHead;
//    while (k--)
//    {
//        if (fast)
//        {
//            fast = fast->next;
//        }
//        else
//        {
//            return NULL;
//        }
//    }
//    while (fast)
//    {
//        fast = fast->next;
//        show = show->next;
//    }
//    return show;
//}

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
//示例 1：
//输入：l1 = [1, 2, 4], l2 = [1, 3, 4]
//输出：[1, 1, 2, 3, 4, 4]
//示例 2：
//输入：l1 = [], l2 = []
//输出：[]
//示例 3：
//输入：l1 = [], l2 = [0]
//输出：[0]


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head1 = list1;
    struct ListNode* head2 = list2;
    struct ListNode* newhead = NULL;
    struct ListNode* tail = NULL;
    while (head1 && head2)
    {
        if (head1->val > head2->val)
        {
            if (newhead == NULL)
            {
                newhead = tail = head2;
            }
            else
            {
                tail->next = head2;
                tail = tail->next;
            }
            head2 = head2->next;
        }
        else
        {
            if (newhead == NULL)
            {
                newhead = tail = head1;
            }
            else
            {
                tail->next = head1;
                tail = tail->next;
            }
            head1 = head1->next;
        }
    }
    if (head1 == NULL && head2)
    {
        if (newhead == NULL)
        {
            newhead = head2;
        }
        else
        {
            tail->next = head2;
        }
    }
    else if (head2 == NULL && head1)
    {
        if (newhead == NULL)
        {
            newhead = head1;
        }
        else
        {
            tail->next = head1;
        }

    }
    return newhead;
}